package com.algorithm.串匹配;

public class 蛮力 {
    public static void main(String[] args) {
        String s1 = "Hello World";
        String s2 = "or";
        System.out.println(indexOf(s1, s2));
    }

    /**
     * 逐个字符逐个字符的进行比较
     *
     * @param text
     * @param pattern
     * @return
     */
    public static int indexOf(String text, String pattern) {
        if (text == null || pattern == null) return -1;

        char[] textChars = text.toCharArray();
        int tlen = textChars.length;
        if (tlen == 0) return -1;
        char[] patternChars = pattern.toCharArray();
        int plen = patternChars.length;
        if (plen == 0) return -1;

        if (plen > tlen) return -1;

        int pi = 0, ti = 0;
        while (pi < plen && ti < tlen) {
            if (textChars[ti] == patternChars[pi]) {
                pi++;
                ti++;
            } else {
                ti -= pi - 1;
                pi = 0;
            }
        }
        return (pi == plen) ? (ti - pi) : -1;
    }


    /**
     * 暴力匹配字符串的优化
     * @param text
     * @param pattern
     * @return
     */
    public static int indexOf2(String text, String pattern) {
        if (text == null || pattern == null) return -1;

        char[] textChars = text.toCharArray();
        int tlen = textChars.length;
        if (tlen == 0) return -1;
        char[] patternChars = pattern.toCharArray();
        int plen = patternChars.length;
        if (plen == 0) return -1;

        if (plen > tlen) return -1;

        int pi = 0, ti = 0;

        // ti - pi: (文本串正在匹配的子串的开始索引)
        // tlen - plen: (开始索引的临界值)
        // tlen - plen为临界值，保证ti - pi始终小于这个临界值，那么说明tlen未比较的长度大于plen
        // ti - pi <= tlen - plen
        int lenDelte = tlen - plen;
        while (pi < plen && ti - pi <= lenDelte) {
            if (textChars[ti] == patternChars[pi]) {
                pi++;
                ti++;
            } else {
                ti -= pi - 1;
                pi = 0;
            }
        }
        return (pi == plen) ? (ti - pi) : -1;
    }
}
